package com.aqie.easy.doublePointer;

/**
 * 28 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 *  返回目标字符串起始索引  todo
 */
public class StrStr {
    /**
     * 1, API  1ms
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

    /**
     * 2, KMP  4ms
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr2(String haystack, String needle) {
        //如果needle为空，则返回0
        if(needle.length()<1){
            return 0;
        }
        if(haystack == null || haystack.length() < 1){
            return -1;
        }

        //主字符串haystack的下标
        int index1 = 0;
        //模式串needle的下标
        int index2 = 0;
        char[] char1 = haystack.toCharArray();
        char[] char2 = needle.toCharArray();
        //获得nexts数组
        int[] nexts = getNexts(char2);
        while(index1 < char1.length && index2 < char2.length){
            if(char1[index1] == char2[index2]){
                index1++;
                index2++;
            }else if(nexts[index2] == -1){//如果为第一位都不匹配则直接下一个字符
                index1++;
            }else{
                index2 = nexts[index2];
            }
        }
        return index2 == char2.length ? index1 - index2 : -1;
    }
    //获得next数组
    private int[] getNexts(char[] str2){
        if(str2.length == 1){
            return new int[]{-1};
        }
        int[] nexts = new int[str2.length];
        nexts[0] = -1;
        nexts[1] = 0;
        //指向当前元素最长前缀的指
        int cn = 0;
        //遍历字符串时的下标
        int index = 2;
        while(index < str2.length){
            if(str2[index - 1] == str2[cn]){
                nexts[index++] = ++cn;
            }else if(cn > 0){
                cn = nexts[cn];
            }else{
                nexts[index++] = 0;
            }
        }
        return nexts;
    }
}
